package com.openess.bigsearch.engine.utils.sort;

import java.util.Comparator;

/**
 * 快速排序
 * 
 * @author TuTu
 * 
 */
public class QuickSort<E> implements Sort<E> {
	/**
	 * 利用快排算法进行排序，排序算法利用了分治思想
	 * 
	 * @param array
	 *            待排序的数组
	 * @param p
	 *            分割的起始位置，包括p
	 * @param r
	 *            分割的终止位置，包括r
	 */
	public void sort(E[] array, int p, int r, Comparator<? super E> c) {
		// 必须有一个判断，用来结束递归，负责就会栈溢出错误
		if (p < r) {
			// 得到分割点的位置
			int position = partition(array, p, r, c);
			sort(array, p, position - 1, c);
			sort(array, position + 1, r, c);
		}
	}

	/**
	 * 快排的关键部分，数组划分，这里采用了随机数选取分割点，使得分割更均称。使得实际运行效率更接近期望时间复杂度。程序运行时，不仅选取定了分割点，
	 * 并且将数组array进行重排，小于分割点的元素全部放在其左侧，大于的放在右侧
	 * 
	 * @param array
	 *            待分割的数组
	 * @param p
	 *            分割的起始位置
	 * @param r
	 *            分割的终止位置
	 * @return 返回数组经过调整后，最终分割点所在的位置
	 */
	public int partition(E[] array, int p, int r, Comparator<? super E> c) {
		// 取[p,r]的随机数，拿其位置上的元素作为分割值
		int random = (int) (Math.random() * (r + 1 - p) + p);
		// 将radom上的元素和r位置上的元素交换位置，因为取分割值始终在r位置上
		E temp = array[random];
		array[random] = array[r];
		array[r] = temp;

		// 分割点，始终选取r
		E breakpoint = array[r];
		int i = p - 1;
		for (int j = p; j <= r - 1; j++) {
			if (c.compare(array[j], breakpoint) < 0) {
				i++;
				// 将A[i]和A[j]进行交换
				E swap = array[i];
				array[i] = array[j];
				array[j] = swap;
			}
		}
		// i+1 为数组经过移位后最终分割点的位置，因此需要将r和最终的分割位置元素进行交换
		array[r] = array[i + 1];
		array[i + 1] = breakpoint;
		return i + 1;
	}
}
